Коды Голомба

Коды Голомба — семейство энтропийных кодов. Под кодом Голомба может подразумеваться также один из представителей этого семейства.

Рассмотрим источник, независимым образом порождающий целые неотрицательные числа [math]\displaystyle{ i }[/math] с вероятностями [math]\displaystyle{ P(i) = (1-p)p^{i} }[/math], где [math]\displaystyle{ p }[/math] — произвольное положительное число, не превосходящее 1, то есть источник, описываемый геометрическим распределением. Если при этом целое положительное число [math]\displaystyle{ m }[/math] таково, что

[math]\displaystyle{ p^m = \frac 1 2 }[/math],

то оптимальным посимвольным кодом (то есть кодом, ставящим в соответствие каждому кодируемому символу определённое кодовое слово) для такого источника будет код, построенный в соответствии с предложенной Соломоном Голомбом процедурой, согласно которой для любого кодируемого числа [math]\displaystyle{ n }[/math] при известном [math]\displaystyle{ m }[/math] кодовое слово образуют унарная запись числа [math]\displaystyle{ q = \left[ \frac{n}{m}\right] }[/math] и кодированный в соответствии с описанной ниже процедурой остаток [math]\displaystyle{ r }[/math] от деления [math]\displaystyle{ \frac{n}{m} }[/math]:

1. Если [math]\displaystyle{ m }[/math] является степенью числа 2, то код остатка представляет собой двоичную запись числа [math]\displaystyle{ r }[/math], размещённую в [math]\displaystyle{ \log_2(m) }[/math] битах.
2. Если [math]\displaystyle{ m }[/math] не является степенью 2, вычисляется число [math]\displaystyle{ b = \lceil\log_2(m)\rceil }[/math]. Далее:

Если [math]\displaystyle{ r \lt 2^b-m }[/math], код остатка представляет собой двоичную запись числа [math]\displaystyle{ r }[/math], размещённую в [math]\displaystyle{ b-1 }[/math] битах,

иначе остаток [math]\displaystyle{ r }[/math] кодируется двоичной записью числа [math]\displaystyle{ r+2^b-m }[/math], размещённой в [math]\displaystyle{ b }[/math] битах.

Позже Р. Галлагером и Д. Ван Вурхисом было показано, что предложенный Голомбом код оптимален не только для дискретного набора значений [math]\displaystyle{ p }[/math], удовлетворяющих приведённому выше критерию, но и для любых [math]\displaystyle{ p }[/math], для которых справедливо двойное неравенство

[math]\displaystyle{ p^{m} + p^{m+1} \le 1 \lt p^{m} + p^{m-1} }[/math],

где [math]\displaystyle{ m }[/math] — целое положительное число. Поскольку для любого [math]\displaystyle{ p }[/math] всегда найдётся не более одного значения [math]\displaystyle{ m }[/math], удовлетворяющего приведённому выше неравенству, предложенная С. Голомбом процедура кодирования геометрического источника оказывается оптимальной для любого значения [math]\displaystyle{ p }[/math].

Чрезвычайно простая в реализации, но не всегда оптимальная разновидность кода Голомба в случае, когда [math]\displaystyle{ m }[/math] является степенью 2, называется кодом Райса.

Пример

Пусть [math]\displaystyle{ p = 0.85 }[/math], требуется закодировать число [math]\displaystyle{ n = 13 }[/math].

Удовлетворяющее двойному неравенству Галлагера — Ван Вурхиса значение [math]\displaystyle{ m = 4 }[/math].

В соответствии с описанной выше процедурой кодирования кодовое слово, соответствующее кодируемому числу 13, строится как унарная запись частного от деления n/m:

[math]\displaystyle{ q = \left[ \frac{n}{m} \right] = \left[\frac{13}{4} \right] = 3 }[/math],

(унарный код [math]\displaystyle{ 0001 }[/math], то есть q нулей с завершающей единицей),

и кодированного остатка

[math]\displaystyle{ r = 1 }[/math],

(код [math]\displaystyle{ 01 }[/math], то есть собственно остаток, записанный в [math]\displaystyle{ \lceil\log_2(m)\rceil }[/math] битах).

Результирующее кодовое слово

[math]\displaystyle{ 0001|01 }[/math]

См. также

• Экспоненциальный код Голомба

Ссылки

• S. W. Golomb. Run-length encodings // IEEE Trans. Inf. Theor. — 1966. — № 3, IT-12. — P. 399—401.
• R. G. Gallager, D. C. Van Voorhis. Optimal source codes for geometrically distributed integer alphabets // IEEE Trans. Inf. Theor. — 1975. — № 2, IT-21. — P. 228—230.
• R. F. Rice, J. R. Plaunt. Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data // IEEE Trans. on Commun. — 1971. — Vol. 16(9). — P. 889—897.
• 2.3 Golomb Codes / Amir Said, On the Determination of Optimal Parameterized Prefix Codes for Adaptive Entropy Coding. HPL-2006-74